The growing use of computer-processed data base information systems has increased the use of digital storage and digital transmission systems by a large factor. Moreover, such use will undoubtedly increase even faster in the future as the information age unfolds. Any reduction, therefore, in the amount of secondary storage facilities or in the bandwidth of the transmission facilities required for this increased information usage will have significant economic effects.
Much stored or transmitted data is redundant. The English language, for example, or a programming language, includes "words" which are often reused. One type of coding which takes advantage of this redundancy is the so-called Huffman code, described in "A Method for the Construction of Minimum Redundancy Codes," by D. A. Huffman, 40 Proc. IRE 1098, September, 1952. In the Huffman scheme, variable length code words are used, the length of the code word being related to the frequency of occurrence of the encoded symbol. Unfortunately, the Huffman approach requires two passes over the data, one to establish the frequency of occurrence of the symbols and another to do the actual encoding. Moreover, the Huffman technique requires temporary storage for the entire data block while the first pass is taken, as well as incurring a corresponding time delay.